The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for providing a transactional memory system that supports unbroken suspended execution.
In speculative parallelization systems, also known as thread-level speculation (TLS) or multi-scalar systems, a compiler, runtime system, or programmer may divide the execution of a program among multiple threads, i.e. separately managed sequences of instructions that may execute in parallel with other sequences of instructions (or “threads”), with the expectation that those threads will usually be independent, meaning that no thread will write data that other threads are reading or writing concurrently. Due to the difficulty in statically determining the memory locations that will be accessed by threads at compilation time, this expectation is not always met. The parallel threads may actually make conflicting data accesses. Such parallelization systems use speculative execution to attempt to execute such threads in parallel. It is the responsibility of the system to detect when two speculative threads make conflicting data accesses, and recover from such a mis-speculation.
Each parallel thread corresponds to a segment of the original sequential code, and the parallel threads are therefore ordered with respect to one another according to their sequence in the sequential version of code. It is the responsibility of the system to ensure that the results of a speculative thread are not committed until all prior speculative threads in this sequence are known to be free of conflicts with the committing thread. Once it has been determined that the thread does not conflict with any threads in the prior sequence, and prior threads have committed, that thread may commit.
Systems that support transactional memory typically include a subset of the requirements of a system that supports speculative parallelization. Transactional memory attempts to simplify concurrent or parallel programming by allowing a group of load and store instructions to execute in an atomic manner, i.e. it is guaranteed that either (1) all instructions of the transaction complete successfully or (2) no effects of the instructions of the transactions occur, i.e. the transaction is aborted and any changes made by the execution of the instructions in the transaction are rolled-back. In this way, with atomic transactions, the instructions of the transaction appear to occur all at once in a single instant between invocation and results being generated.
Hardware transactional memory systems may have modifications to the processors, caches, and bus protocols to support transactions or transaction blocks, i.e. groups of instructions that are to be executed atomically as one unit. Software transactional memory provides transactional memory semantics in a software runtime library with minimal hardware support.
As described in Bobba et al., “Performance Pathologies in Hardware Transactional Memory,” ISCA '07, Jun. 9-13, 2007, a programmer can invoke a transaction in a multi-threaded application and rely on the transactional memory system to make its execution appear atomic in a global serial order. Bobba et al. discusses conflict resolution policies in transactional memory systems, however, the concept of transactional memory was introduced by Herlihy and Moss “Transactional Memory: Architectural Support for Lock-Free Data Structures,” Proceedings of the 20th Annual International Symposium on Computer Architecture, pp. 289-300, May 1993.
Transactional memory systems seek high performance by speculatively executing transactions concurrently and only committing transactions that are non-conflicting. A conflict occurs when two or more concurrent transactions access the same piece of data, e.g. a word, block, object, etc., and at least one access is a write. Transactional memory systems may resolve some conflicts by stalling one or more transactions.
Transactional blocks are typically demarcated in a program with special transaction begin and end annotations. Transactional blocks may be uniquely identified by a static identifier, e.g., the address of the first instruction in the transactional block. Dynamically, multiple threads can concurrently enter a transactional block, although that transactional block will still share the same static identifier.
In addition to the ability to revert, or roll-back, changes made to memory and registers made during the speculative execution of a transaction, transactional memory systems often support the detection of conflicting accesses made by speculative threads. However, maintaining the proper ordering of speculative threads is not naturally supported by transactional memory systems. Because a transaction should not commit until prior speculative threads in the sequence have committed, some communication among speculative threads is required. However, by definition, transactions are intended to be isolated from one another such that any communication amongst transaction threads through shared memory will cause the transactions to be aborted.